//
// Description: 5944. 从二叉树一个节点到另一个节点每一步的方向
// Created by Loading on 2021/12/5.
//

#include <bits/stdc++.h>
#include <Data_Structure_Definition.h>
#include <Utils.h>

using namespace std;

/* 去除前缀 */
string getDirections(TreeNode *root, int startValue, int destValue) {
    /*
     * 查找根节点到两个节点的路径，公共前缀为根节点到两个节点的最近公共父节点的路径，
     * 删除公共前缀后将起始节点剩余路径全部改为'U'，并拼接目标节点剩余路径，即为答案
     */
    // 查找路径方法
    function<bool(TreeNode *, int, string&)> find = [&](TreeNode *node, int target, string &s) {
        if (!node) {
            return false;
        }
        if (node->val == target) {
            return true;
        }
        if (node->left) {
            s += 'L';
            if (find(node->left, target, s)) {
                return true;
            }
            s.pop_back();
        }
        if (node->right) {
            s += 'R';
            if (find(node->right, target, s)) {
                return true;
            }
            s.pop_back();
        }
        return false;
    };

    string s_startValue, s_destValue;
    // 查找根节点分别到两个节点的路径
    find(root, startValue, s_startValue);
    find(root, destValue, s_destValue);

    int index = 0;
    while (index < s_startValue.size() && index < s_destValue.size() && s_startValue[index] == s_destValue[index]) {
        ++index;
    }
    // 去掉公共前缀
    s_startValue = s_startValue.substr(index);
    s_destValue = s_destValue.substr(index);

    string res(s_startValue.size(), 'U');
    return res + s_destValue;
}

/* DFS + 回溯 */
string getDirections_DFS(TreeNode *root, int startValue, int destValue) {
    // 存储每个节点的左子树节点、右子树节点、父节点
    unordered_map<int, vector<int>> m;
    function<void(TreeNode *, int)> find = [&](TreeNode *node, int father) {
        if (!node) {
            return;
        }
        vector<int> v(3, -1);
        v[2] = father;
        if (node->left) {
            v[0] = node->left->val;
        }
        if (node->right) {
            v[1] = node->right->val;
        }
        m[node->val] = v;
        find(node->left, node->val);
        find(node->right, node->val);
    };

    find(root, -1);

    string res;
    // 是否已找到
    bool flag = false;
    // val 为当前遍历的节点，pre 为上一个遍历的节点
    function<void(int, int)> dfs = [&](int val, int pre) {
        if (val == destValue) {
            flag = true;
            return;
        }
        // 存在左子树，且左子树不为上一个遍历的节点
        if (m[val][0] != -1 && m[val][0] != pre) {
            res.push_back('L');
            dfs(m[val][0], val);
        }
        // 找到则跳出
        if (flag) {
            return;
        }
        // 未找到则回溯
        if (m[val][0] != -1 && m[val][0] != pre && !res.empty()) {
            res.pop_back();
        }
        if (m[val][1] != -1 && m[val][1] != pre) {
            res.push_back('R');
            dfs(m[val][1], val);
        }
        if (flag) {
            return;
        }
        if (m[val][1] != -1 && m[val][1] != pre && !res.empty()) {
            res.pop_back();
        }
        if (m[val][2] != -1 && m[val][2] != pre) {
            res.push_back('U');
            dfs(m[val][2], val);
        }
    };

    dfs(startValue, -2);
    return res;
}

int main() {
    vector<int> nums = {5, 1, 2, 3, -1, 6, 4};
    auto root = generateTreeNode(nums);
    int startValue = 3;
    int destValue = 6;

    // 去除前缀
    string res = getDirections(root, startValue, destValue);
    cout << res << endl;
    // DFS + 回溯
    res = getDirections_DFS(root, startValue, destValue);
    cout << res << endl;

    return 0;
}